package a07_二叉树;

import sun.reflect.generics.tree.Tree;

import java.util.Arrays;

/**
 * <p>
 * a14_从中序与后序遍历序列构造二叉树
 * </p>
 *
 * @author flyduck
 * @since 2024-09-10
 */
public class a18_从中序与后序遍历序列构造二叉树 {

    public static void main(String[] args) {
        int[] inorder = {9,3,15,20,7};
        int[] postorder = {9,15,7,20,3};
        TreeNode treeNode = buildTree(inorder, postorder);
        System.out.println();
    }

    //中序：左中右 9,3,15,20,7
        //不知道中在哪
        //看后序的最后是3，所以3就是跟节点
        //看中序左区间就是9，右区间就是15,20,7
        //看后序里面的15,20,7，发现20在最后，所以20就是中
        //看中序，20切割后，15是左，7就是右节点了
    //后序：左右中 9,15,7,20,3
    //步骤：
    //1、postorder为空，返回null
    //2、postorder最后一个元素作为根节点
    //3、在inorder找到根节点
    //4、然后用根节点切割inorder得到左区间和右区间
    //5、用左区间和右区间切割postorder
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length == 0) {
            return null;
        }

        int rootValue = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootValue);

        int rootIdx = 0;
        while (rootIdx < inorder.length) {
            if(inorder[rootIdx] == rootValue){
                break;
            }else {
                rootIdx++;
            }
        }

        int[] leftInorder = splitArray(inorder, 0, rootIdx - 1);
        int[] rightInorder = splitArray(inorder, rootIdx + 1, inorder.length - 1);

        int[] leftPostorder = splitArray(postorder, 0, leftInorder.length - 1);
        int[] rightPostorder = splitArray(postorder, leftInorder.length, postorder.length - 2);

        TreeNode leftNode = buildTree(leftInorder, leftPostorder);
        TreeNode rightNode = buildTree(rightInorder, rightPostorder);

        root.left = leftNode;
        root.right = rightNode;
        return root;
    }

    public static int[] splitArray(int[] oldArray,int leftIdx,int rightIdx){
        int[] newArray = new int[rightIdx - leftIdx + 1];
        for (int i = 0; i < newArray.length; i++) {
            newArray[i] = oldArray[leftIdx];
            leftIdx++;
        }
        return newArray;
    }




}
